/*
 * @FilePath: \undefinedc:\Users\sxjct\.leetcode\92.反转链表-ii.cpp
 * @Brief: 
 * @Version: 1.0
 * @Date: 2021-03-02 17:23:40
 * @Author: tianyiyi
 * @Copyright: Copyright@tianyiyi
 * @LastEditors: Mr.Tian
 * @LastEditTime: 2021-03-18 19:12:12
 */
// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem92.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=92 lang=cpp
 *
 * [92] 反转链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
// class Solution {
// private:
//     ListNode* successor;  //存储后驱节点
// public:
//     ListNode* reserve(ListNode* head)
//     {
//         if(head == NULL)
//             return NULL;
//         ListNode* last = reserve(head->next);
//         head->next->next = head;
//         head->next = NULL;
//         return last;
//     }

//     ListNode* reverseN(ListNode* head,int n)
//     {
//         if(n == 1)
//         {
//             // 不进行任何交换
//             successor = head->next;
//             return head;
//         }
//         ListNode* last = reverseN(head->next,n-1);
//         head->next->next = head;
//         head->next = successor;
//         return last;
//     }

//     ListNode* reverseBetween(ListNode* head, int left, int right) {

//         if(left == 1)
//         {
//             return reverseN(head,right);
//         }
//         head->next = reverseBetween(head->next,left-1,right-1);
//         return head;
//     }
// };

class Solution {
private:
public:
    ListNode* reverseBetween(ListNode* head, int left, int right)
    {
        ListNode *guard = new ListNode(0);
        guard->next = head;

        ListNode* p = head;
        ListNode* pre = guard;

        int step = 0;
        while(step < left - 1)
        {
            step++;
            pre = pre->next;
            p = p->next;
        }
    
        for(int i = 0; i < right - left;i++)
        {
            ListNode *r = p->next;
            p->next = r->next;
            
            r->next = pre->next;
            pre->next = r;
        }
        return guard->next;
    }
    
};


// @lc code=end

